package leetcode;

/**
 * 最长回文子串  
 */
public class LeetCode5 {
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        int len = s.length();
        String word = "";
        boolean[][] arr = new boolean[len][len];
        for (int i = len - 1; i >= 0; i--) {
            for (int j = i; j < len; j++) {
                if (s.charAt(i) != s.charAt(j)) {
                    continue;
                }
                if (j - i < 2 || arr[i + 1][j - 1]) {
                    arr[i][j] = true;
                }
                if (arr[i][j] && j - i + 1 > word.length()) {
                    word = s.substring(i, j + 1);
                }
            }
        }
        return word;
    }

    public String longestPalindrome1(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        int len = s.length();
        String word = "";
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len + 1; j++) {
                if (isPalindrome(s.substring(i, j)) && j - i > word.length()) {
                    word = s.substring(i, j);
                }
            }
        }
        return word;
    }

    public String longestPalindrome2(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        int len = s.length();
        String word = "";
        for (int i = 0; i < len; i++) {

        }
        return word;
    }

    private boolean isPalindrome(String s) {
        return s.equals(new StringBuilder(s).reverse().toString());
    }

    public static void main(String[] args) {
        LeetCode5 leetCode05 = new LeetCode5();
        System.out.println(leetCode05.longestPalindrome("abbcccc"));
    }
}
